package leetcode.d29;

//好难


//请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
//["10", "0001", "111001", "1", "0"] m=5,n=3
public class Solution {
    public static int findMaxForm(String[] strs, int m, int n) {
        int length = strs.length;
        int[][] d = new int[m + 1][n + 1];
        for (int i = 0; i < length; i++) {
                //先求1和0的数量
                char[] chars = strs[i].toCharArray();
                int l = 0,o=0;
                for (char aChar : chars) {
                    if (aChar=='1'){
                        l++;
                    }
                    else{
                        o++;
                    }
                }
                for (int x=m;x>=o;x--){
                    for (int y = n;y>=l;y--){
                        d[x][y] = Integer.max(d[x][y],d[x-o][y-l]+1);
                    }
                }
        }
        return d[m][n];
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int maxForm = findMaxForm(strs, 5, 3);
        System.out.println(maxForm);
    }
}
